class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m=mat.length,n=mat[0].length;
        int[][] arr=new int[m+1][n+1];
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                arr[i][j]=arr[i][j-1]+arr[i-1][j]-arr[i-1][j-1]+mat[i-1][j-1];
            }
        }



        int[][] ret=new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                int x1=Math.max(0,i-k),y1=Math.max(0,j-k);
                int x2=Math.min(i+k+1,m),y2=Math.min(j+k+1,n);
                ret[i][j]=arr[x2][y2]-arr[x2][y1]-arr[x1][y2]+arr[x1][y1];
            }
        }

        return ret;





    }
}